基础算法模板：
1.高精算法：
加法：
while(i<=a加数的位数|| i<=b加数的位数)
{ c[i]=a[i]+b[i]+x;
x=c[i]/10;
c[i]%=10;
i++;
}
注意：加法需要逆序储存，因为如果正序储存，那么当加数相加会超过数组的范围。
减法：
While(lenc<=lena||lenc<=lenb)
{
If(a[i]<b[i])
{
a[i]+=10;
a[i+1]--;
}
c[i]=a[i]-b[i];
i++;
}
乘法：
for(i=1;i<=lena;i++)
{
x=0;
for(j=1;j<=lenb；j++)
{
c[i+j-1]=a[i]*b[j]+x+c[i+j-1];
x=c[i+j-1]/10;
c[i+j-1]%10;
}
c[i+lenb]=x;
}
Lenc=lena+lenb;
2.排序
<1>桶排序
#include<iostream>
using namespace std;
int a[10001];
int n,k;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>k;
a[k]++;
}
for(int i=1;i<=10000;i++)
{
while(a[i]>0)
{
cout<<i<<" ";
a[i]--;
}
}
return 0;
}
桶排序算法，复杂度为常数。特别快但是要注意空间。适当的时候用哈希的思想来解决。比如排序：1 4 100000000 7.一共就4个元素但是如果用正常的桶排序的话就要开一个100000001的数组，太费空间。不如就哈希一下。
<2>快排
#include<iostream>
using namespace std;
void qsort(int,int);
int n;
int a[1001];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
qsort(1,n);
for(int i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
void qsort(int l,int r)
{
int i,j,mid,p;
i=1;
j=r;
mid=a[(l+r)/2];
do
{
while(a[i]<mid) i++;
while(a[j]>mid) j--;
if(i<=j)
{
p=a[i];
a[i]=a[j];
a[j]=p;
i++;
j--;
}
}while(i<=j);
if(1<j) qsort(l,j); //这里是一不是L
if(i<r) qsort(i,r);
}
快排的思想在于首先是把数先正好顺序的排列一下。然后一个从头找，一个从找，当前面的大于中间值，后面的小于中间值。这两个交换。当然就有疑问当后面值交换过来比前面的值小怎么办。后面的两个if语句就可以解决这种情况。
<3>归并排序
#include<iostream>
using namespace std;
int a[101],r[101];
void mergesort (int ,int);
int main()
{
int n,i;
cin>>n;
for(i=1;i<=n;i++)
cin>>a[i];
mergesort(1,n);
for(i=1;i<=n;i++)
cout<<a[i]<<" ";
return 0;
}
void mergesort (int s,int t)
{
int m,i,j,k;
if(s==t) return ;
m=(s+t)/2;
mergesort(s,m);
mergesort(m+1,t);
i=s;
j=m+1;
k=s;
while(i<=m && j<=t)
{
if(a[i]<=a[j])
{
r[k]=a[i];
i++;
k++;
}
else
{
r[k]=a[j];
j++;
k++;
}
}
while(i<=m)
{
r[k]=a[i];
i++;
k++;
}
while(j<=t)
{
r[k]=a[j];
j++;
k++;
}
for(i=s;i<=t;i++) a[i]=r[i];
}
归并排序在于利用另一个数组进行排序。利用二分查找的思想来实现。一开始二分二分从第一个开始在一个范围里进行排序，使得在这一个区域里所有的数字以升序排列。返回这个序列给上一次调用，然后与上一层调用在以升序。以此类推到最后则调用结束。
3.递推
<1>斐波那契数列：
F[x]=f[x-1]+f[x-2];
边界条件：f[0]=0,f[1]=1;
前几项数据：0,1,1,2,3,5,8,13,21……
<2>汉罗塔问题：
H[n]=2*H[n-1]+1;
边界：H[1]=1;
前几项数据：1,3,7,15,31,63……
<3>平面分割问题：
A[n]=A[n-1]+2*(n-1);
边界：A[1]=1;
前几项数据：1,3,7,13,21,31……
<4>Catalan数
<5>第二类Stirling数
4.搜索与回溯
int dfs(int k)
{
for(int i=1;i<=n;i++)
{
if(符合要求 )
{
进行标记
if(到达目的地)
输出
else
dfs（）；
恢复标记。
}
}
}
int dfs(int k)
{
if(到达目的地)
输出
for(int i=1;i<=n;i++)
{
if(符合条件 )
{
保存标记
dfs();
取消标记
}
}
}
5.贪心与分治
贪心思想：贪心是局部最优解最后推算到全局最优解得过程对最终结果无影响则可以使用。必须给出严格的数学证明。
分治思想：把一个大问题化解成多个小问题，然后在把问题的解合起来组成最后的解。例如归并排序。
6.广度优先搜索
int bfs()
{
int head,tail;
head=0;tail=1;
while(head<tail)
{
head++
for(int i=1;i<=目标 ;i++)
if(v[i]==0 && map[a[head]][i]==0)
{
tail++;
a[tail]=i;
b[tail]=head;
v[i]=1;
if(i==目标 )
{
输出解
head=tail;
break;
}}}}
}
7.动态规划
for(int i=1;i<=目标 ;i++)
for(int j=1;j<= 目标;j++)
for(int k=1;k<=目标 ;k++)
f[j]=max(f[j],f[j-v[i]]+k*w[i]);
cout<<f[n]<<endl;
0-1背包：注意为倒序
完全背包：为正序
多重背包：为倒序多个添加一个循环
说实话对于动态规划的话，没有什么固定的算法，因为他只是一种思想，没错就是一种思想。所谓的动归，也是一种搜索的系列。只不过它的每一次搜索都会进行储存，但跟记忆化搜索不一样。比如说你有78元钱，我问你这78元钱有多少种组成方案？记忆化搜索一般跟递归搭配。思想不就是，首先从1开始，然后将搜索到的内容存到一个数组里，当再次调用时出来就ok了。而动归的思想在于，我78元钱我不知道怎么分，但是1块钱我知道块分。1块钱的组成方案不就是1张一块的。然后到2块钱，2张1块。以此类推，后一种阶段需要前一种阶段的解读。这样当我知道78元的方案，同时在76的方案数我也计算出来了。这样可以将大规模的数据进行压缩。当然每一次的选择要找最优的（并不是局部最优），例如：当我有abcde五个点，a可以到b，c，c可以到d，b也可以到d。而d可以到e。因为bc两个点都可以到c所以， 比较b，c两条路的长度，选择最优的，因为这样就可以与后面的决策无关。从而选出最优的一条路。这也是dijskra的单源最短路算法的思想。\
栈、队列
关于栈的定义就是说，只能在一段进行插入或删除的特殊线性表。
进栈：
If(top<=n) //栈是否溢出？
{
Top++;
S[top]=x; //入栈
}
退栈：
If(top>=0) //判断栈是否为空？
{
X=s[top];
Top--; //出栈；
}
队列是指在限定的一段进行插入，另一端进行删除的特殊线性表。
常和BFS进行搭配。
图论
<1>有向图邻接矩阵存储：map[x][y]=z;
无向图邻接矩阵储存：map[x][y]= map[y][x]=z;
Double memset(map,127,sizeof(map));
Int memset(map,0x7f,sizeof(map);
<2>强连通分量：1à2à3à1
在邻接矩阵中： 01102
00102
00022
00002
上面的有向图邻接矩阵共有两个连通分量。后面有关于代码的实现。
<3>邻接表储存
#include<iostream>
#define maxn 1001
using namespace std;
struct Edge
{
int next;//下一个点；
int to;//这条边所到达的点；
int dis;//边的长度；
}edge[maxn];
int head[maxn],num,n,m,u,v,d;
void add_edge(int from,int to,int dis)
{
num++;
edge[num].next=head[from];
edge[num].to=to;
edge[num].dis=dis;
head[from]=num;
}
int main()
{
num=0;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>u>>v>>d;
add_edge(u,v,d);
}
for(int i=head[i];i!=0;i=edge[i].next)
{
//add 其他代码；
}
return 0;
}
本方法的储存方法比较费脑子，有一点逻辑思维。存储时为正序存储，读取时为逆序。
Next
To
Dis
0
2
6
1
3
5
2
4
11
Head[from]=0
Head[from]=1
Head[from]=2
读入的样例：1 2 6
1 3 5
1 4 11
<4>图论的遍历
Dfs（）；从一个点开始，访问一个点，并把此点标记，递归访问下一个，并回朔一步。
关于连通分量的代码：
for(int i=1;i<=n;i++)
if(v[i]==0)
{
dfs(i); //bfs(i)枚举一个点进行访问，并标记。
sum++;
}
<4>欧拉道路问题：
定理1：存在欧拉路的条件：图是连通的，并且有2个奇点；
定理2：存在欧拉回路的条件：图是连通的：有0个奇点；
（ps：奇点是连接此点边数有奇数个。）
算法模板：
#include<iostream>
#include<cstring>
#define maxn 1001
using namespace std;
int n,m,start,map[maxn][maxn],x,y,len,c[maxn],ans[maxn];
void dfs (int i)
{
for(int j=1;j<=n;j++)
{
if(map[i][j]==1)
{
map[i][j]=map[j][i]=0;
dfs(j);
}
}
len++;
ans[len]=i;
}
int main()
{
memset(map,0,sizeof(map));
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
map[x][y]=map[y][x]=1;
c[x]++;
c[y]++;
}
start=1;
for(int i=1;i<=n;i++)
if(c[i]%2==1)
start=i;
len=0;
dfs(start);
for(int i=1;i<=len;i++)
cout<<ans[i]<<" ";
return 0;
}
<5>哈密尔顿环
算法模板：
#include<iostream>
#include<cstring>
#define maxn 1001
using namespace std;
int len,x,y,ans[maxn],map[maxn][maxn];
int v[maxn],vis[maxn],num[maxn],n,m,start;
void dfs (int last,int i)
{
vis[i]=1;
v[i]=1;
len++;
ans[len]=i;
for(int j=1;j<=num[i];j++)
{
if(map[i][j]==start && map[i][j]!=last)
{
ans[len+1]=start;
for(int i=1;i<=len+1;i++)
cout<<ans[i]<<" ";
break;
}
if(vis[map[i][j]]==0) dfs(i,map[i][j]);
}
len--;
vis[i]=0;
}
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
cin>>x>>y;
map[x][++num[x]]=y;
map[y][++num[y]]=x;
}
for(start=1;start<=n;start++)
{
if(v[start]==0)
{
len=0;
dfs(0,start);
}
}
return 0;
}
呼呼呼山(http://code4fun.me)
11 Jan 2018 10:49 PM